package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         169,
		Discription: "个数大于n/2的元素（保证有解)",
		Level:       1,
		Labels: map[string]int{
			"贪心": 1,
		},
	})
}

func MajorityElement(nums []int) int {
	candidate := nums[0]
	count := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == candidate {
			count++
			continue
		}

		count--
		if count == 0 {
			candidate = nums[i]
			count++
		}
	}

	return candidate
}
